#include<iostream>
using namespace std;

typedef unsigned int uint;

/* calc a^b % n */
uint ExponentMod(uint a, uint b, uint n)
{
	uint bitFlag[32] = {0};
	int nBitWidth = 0;
	
	while (0 != b)
	{
		bitFlag[nBitWidth] = b & 1;
		b >>= 1;
		nBitWidth++;
	}
	
	uint c = 0;
	uint d = 1;
	for (int k = nBitWidth - 1; k >= 0; k--)
	{
		c <<= 1;
		d = (d * d) % n;
		
		if (1 == bitFlag[k])
		{
			c ++;
			d = (d * a) % n;
		}
	}
	
	return d;
}

int main(void)
{
	cout<< ExponentMod(7, 560, 561)<<endl;
}
